package com.example.leetcode.linklist;


/**
 * 合并两个排序的链表
 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 输入：
 * {1,3,5},{2,4,6}
 * 复制
 * 返回值：
 * {1,2,3,4,5,6}
 */

public class MergeList {


    public static void main(String[] args) {
        ListNode pHead1 = new ListNode(1);
        ListNode pHead11 = new ListNode(3);
        ListNode pHead111 = new ListNode(5);
        pHead1.setNext(pHead11);
        pHead11.setNext(pHead111);

        ListNode pHead2 = new ListNode(2);
        ListNode pHead22 = new ListNode(4);
        ListNode pHead222 = new ListNode(6);
        pHead2.setNext(pHead22);
        pHead22.setNext(pHead222);

        ListNode merge = Merge(pHead1, pHead2);
        System.out.println();
    }

    public static ListNode Merge2(ListNode pHead1, ListNode pHead2) {
        // 返回新的链表，构造一个头节点
        if (pHead1 == null) {
            return pHead2;
        }

        if (pHead2 == null) {
            return pHead1;
        }

        ListNode head = new ListNode(-111);
        ListNode current = head;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                current.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                current.next = pHead2;
                pHead2 = pHead2.next;
            }
            current = current.next;
        }

        if (pHead1 == null) {
            current.next = pHead2;
        }
        if (pHead2 == null) {
            current.next = pHead1;
        }

        return current.next;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public static ListNode Merge(ListNode pHead1, ListNode pHead2) {
        // 返回新的链表，构造一个头节点
        if (pHead1 == null) {
            return pHead2;
        }

        if (pHead2 == null) {
            return pHead1;
        }

        ListNode head = new ListNode(0);
        ListNode current = head;

        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                current.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                current.next = pHead2;
                pHead2 = pHead2.next;
            }
            current = current.next;
        }

        if (pHead1 == null) {
            current.next = pHead2;
        }
        if (pHead2 == null) {
            current.next = pHead1;
        }

        return head.next;
    }
}
